package 动态规划.递归参数思考型;

public class 买卖股票的最佳时机3 {

	
	
	public int solution(int prices[]) {
		int len = prices.length;
		return recursion(0,0,2,prices,len);
		
	}
	/**
	 * 
	 * @param index  表示时间 ，第 0天， 第一天，第二天
	 * @param status  持股状态 ，0 表示未持股 ，1，表示持股
	 * @param counts  完成 交易 股票的次数， 初始值 传入 2
	 * @param prices 股票 的数组
	 * @param len 
	 * @return  返回的值，含义： cong 当前 index 天 开始到 股市 结束，在 持股状态 status 以及，拥有的 股票交易，次数 为counts
	 * 的最大收益 值：
	 */
	public int recursion(int index,int status,int counts ,int prices[],int len) {
		if(counts == 0 || index == len )
			return 0;
		
		int ans = 0,ans1 = 0;
		if(status  == 0) {
			//  选择 观察， 并不操作
			ans = recursion(index + 1,status,counts,prices,len);
			// 直接出手 买下  当天 股票，
			ans1 = recursion(index + 1,1,counts,prices,len) - prices[index];
		}
		else {
			// 当前 持有股票，但是选择 不出手！
			ans = recursion(index + 1,status,counts,prices,len);
			// 选择 卖掉股票，这里 的counts 要  -1 ，我选择在 卖掉股票的时候认为，是完成了一次交易， 才让拥有的交易次数counts - 1
			// 买入股票，时，并不考虑 ，counts ，这一点有点抽象！
			ans1 = recursion(index + 1,0,counts - 1,prices,len) + prices[index];
		}
		return Math.max(ans, ans1);
	}
	
	/**
	 * 上面这个 暴力递归改成  dp，确实 有点烧脑的！
	 */
	public int dp(int prices[]) {
		int len = prices.length;
		int counts = 3;
		int dp[][][] = new int [len + 1][counts][2];
		
		for(int index = len -1;index >= 0;index--) {
			// 直接从  count = 1 开始， 从 basecase 可以看出， count = 0 返回的值  是 0
			for(int count = 1;count < counts;count ++) {
				dp[index][count][0] = Math.max(dp[index + 1][count][0], dp[index + 1][count][1] - prices[index]);
				dp[index][count][1] = Math.max(dp[index + 1][count][1], dp[index + 1][count - 1][0] + prices[index]);
			}
			
		}
		return dp[0][2][0];	
	}
	
}
